#pragma once

#include <memory>

template <typename T>
class AbstractSort
{
private:
    /* data */
public:
    AbstractSort() = default;
    ~AbstractSort() = default;

    void Sorted(T arr[], int left, int right) {
        if (left >= right) return;
    
        int i = left, j = right;
    
        while (i < j) {
            while (i < j && Compare(arr[j], arr[left])) {
                --j;
                
            }
            while (i < j && Compare(arr[left], arr[i])) {
                ++i;
            }
    
            if (i != j) {
                std::swap(arr[i], arr[j]);
            }
        }
    
        std::swap(arr[left], arr[j]);
        
        Sorted(arr, left, j - 1);
        Sorted(arr, j + 1, right);
    }

    virtual bool Compare(T a, T b) const = 0;
};

template <typename T>
using AbstractSort_ptr = std::shared_ptr<AbstractSort<T>>;